package org.example.myleet.p802;

import java.util.*;

public class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        //记录每个点的出度
        Set<Integer>[] outBoundSets = new Set[graph.length];
        //记录每个点的入度
        Set<Integer>[] inBoundSets = new Set[graph.length];
        //解释图，将所有点的入度和出度分别对应记录
        for (int i = 0; i < graph.length; ++i) {
            int[] edges = graph[i];
            Set<Integer> outBoundSet = Optional.ofNullable(outBoundSets[i]).orElse(new HashSet<>());
            for (int node : edges) {
                outBoundSet.add(node);
                Set<Integer> inBoundSet = Optional.ofNullable(inBoundSets[node]).orElse(new HashSet<>());
                inBoundSet.add(i);
                inBoundSets[node] = inBoundSet;
            }
            outBoundSets[i] = outBoundSet;
        }
        Set<Integer> result = new HashSet<>(graph.length);
        for (int i = 0; i < graph.length; ++i) {
            if (outBoundSets[i].size() < 1) {
                //如果i点的出度是0，说明是一个安全点
                result.add(i);
                //递归地移除指向安全点的边
                removeBound(outBoundSets, inBoundSets, result, i);
            }
        }
        List<Integer> reply = new ArrayList<>(result);
        reply.sort(Comparator.naturalOrder());
        return reply;
    }

    /**
     * 找到一个安全点i，移除指向i的边
     */
    private void removeBound(Set<Integer>[] outBoundSets, Set<Integer>[] inBoundSets, Set<Integer> result, int i) {
        //到达i点的的所有入度
        Set<Integer> inBoundSet = Optional.ofNullable(inBoundSets[i]).orElse(null);
        if (null != inBoundSet) {
            //移除对应的入度中指向i点的边
            for (int inBound : inBoundSet) {
                outBoundSets[inBound].remove(i);
                if (outBoundSets[inBound].size() < 1) {
                    //如果某入度的点的出度变成0，说明也是一个安全点
                    result.add(inBound);
                    removeBound(outBoundSets, inBoundSets, result, inBound);
                }
            }
        }
    }
}
